#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define NodeNum 5		//每个节点的最大子节点数
typedef struct Shape Shape;
struct Shape			//非叶节点的孩子节点所占的区域
{
	int min_x;		//最小x
	int min_y;		//最小y
	int max_x;		//最大x
	int max_y;		//最大y
};

typedef struct Node Node;
struct Node			//节点元素
{
	int x;			//当前元素的x坐标
	int y;			//当前元素的y坐标
	int ChildNum;		//当前元素的子节点数
	Node *parent;		//当前节点的父节点
	Node *child[NodeNum];	//当前节点的子节点
	Shape NShape;		//当前节点的形状
	int level;		//层次
};

Node *rtree;						//全局变量rtree表示R树的根节点

Node *new_leafNode(int x, int y)			//创建叶节点
{
	Node *new = (Node *)malloc(sizeof(Node));	//创建节点
	new->x = x;
	new->y = y;
	new->level = 0;					//层次初始化，在确定parent后再更改
	int i;
	for(i = 0; i < NodeNum; i++)
		new->child[i] = NULL;			//孩子节点设为NULL
	new->parent = NULL;				//父节点设为NULL，在确定插入位置之后再修改
	return new;					//返回
}

Node *new_nonLeafNode()					//创建非叶子节点
{
	Node *tmp = (Node *)malloc(sizeof(Node));
	tmp->ChildNum = 0;				//初始孩子节点数为0
	tmp->level = 1;					//初始化层数为1
	tmp->parent = NULL;				//初始化父节点为NULL
	return tmp;					//返回创建的节点
}

void Travel(Node *curr)					//R树的搜索操作
{
	int icr = curr->ChildNum;			//获取当前节点的子节点数
	if(curr->level >= 2)				//如果当前节点层数大于2
	{
		for(int i = 0; i < icr; i++)		//遍历当前节点的孩子节点
		{
			Node *tmp = curr->child[i];
			Shape shape = curr->NShape;
			Travel(curr->child[i]);		//递归遍历
		}
	}
	else						//当前节点层数为1
	{
		for(int i = 0; i < icr; i++)		//遍历叶节点
		{
			Node *tmp = curr->child[i];
		}
	}
}

Node *AddToMbr(Node *parent, Node *entry)		//添加entry到parent中
{
	if(entry->level == 0)
	{
		int tmp = parent->ChildNum;		//获取当前parent节点的子节点数
		parent->child[tmp] = entry;			//将entry插入到parent中
		parent->ChildNum++;			//节点数加一
		entry->parent = parent;			//设置entry的parent节点
		Shape PS = parent->NShape;
		if(entry->x < PS.min_x)
			PS.min_x = entry->x;
		if(entry->y < PS.min_y)
			PS.min_y = entry->y;
		if(entry->x > PS.max_x)
			PS.max_x = entry->x;
		if(entry->x > PS.max_y)
			PS.max_x = entry->x;
		parent->NShape = PS;
	}
	else
	{
		Shape newS = entry->NShape;
		Shape pS = parent->NShape;
		if(newS.min_x < pS.min_x)	pS.min_x = newS.min_x;
		if(newS.min_y < pS.min_y)	pS.min_y = newS.min_y;
		if(newS.max_x > pS.max_x)	pS.max_x = newS.max_x;
		if(newS.max_y > pS.max_y)	pS.max_y = newS.max_y;
		int tmp = parent->ChildNum;
		parent->child[tmp] = entry;
		parent->ChildNum++;
		entry->parent = parent;
		
	}
	return parent;
}

void SplitNode(Node* parent, Node *newNode, Node *nowNode, Node *curr)//分割节点
{
	if(parent->level > 2)
	{
		Node *point = nowNode;
		Node *ptr = newNode;
		parent = AddToMbr(parent, newNode);	//将新节点插入到parent中
		point = point->child[0];
		int level = point->level;
		while(level >= 1)			//当point所在层数不为0
		{
			Node *tmp = new_nonLeafNode();	//新建一个非叶节点
			tmp->level = level;		//该非叶节点所在层为level
			ptr->ChildNum++;
			ptr->child[0] = tmp;		//将该节点添加到ptr中
			tmp->parent = ptr;
			ptr = ptr->child[0];
			point = point->child[0];
			level = point->level;
		}
	}
	else						//parent层级为2时
	{
		parent = AddToMbr(parent, newNode);	//将节点newNode插入到节点parent中
		int i;
		int xy[NodeNum + 1][2];
		for(i = 0; i < NodeNum; i++)
		{
			int x = nowNode->child[i]->x;
			int y = nowNode->child[i]->y;
			xy[i][0] = x;
			xy[i][1] = y;
		}
		xy[i][0] = curr->x;
		xy[i][1] = curr->y;
		BubbleSort(xy);				//对节点集进行排序
		for(i = 0; i < NodeNum; i++)
			nowNode->child[i] = NULL;	//初始化当前节点
		nowNode->ChildNum = 0;
		int tmpNum = (int)(NodeNum/2);
		for(i = 0; i < tmpNum; i++)
		{
			Node *leaf = new_leafNode(xy[i][0], xy[i][1]);
			nowNode = AddToMbr(nowNode, leaf);
		}
		for(i = tmpNum; i < NodeNum + 1; i++)
		{
			Node *leaf = new_leafNode(xy[i][0], xy[i][1]);
			newNode = AddToMbr(newNode, leaf);
		}
	}
}

void BubbleSort(int xy[NodeNum + 1][2])		//对xy点集进行排序
{
	int i, j, tmp_x, tmp_y;
	for(i = 0; i < NodeNum + 1; i++)
		for(j = 0; j < NodeNum - i; j++)
			if(xy[j][0] > xy[j+1][0])
			{
				tmp_x = xy[j+1][0];
				tmp_y = xy[j+1][1];
				xy[j+1][0] = xy[j][0];
				xy[j+1][1] = xy[j][1];
				xy[j][0] = tmp_x;
				xy[j][1] = tmp_y;
			}
}

void UpdateInfomation(Node *root)			//更新边界值
{
	int icr = root->ChildNum;			//获取当前节点的孩子节点数
	int i;
	int min_x = 100;
	int max_x = 0;
	int min_y = 100;
	int max_y = 0;
	Shape origin = root->NShape;			//获取原Shape
	for(i = 0; i < icr; i++)			//获取边界值
	{
		Shape child = root->child[i]->NShape;
		if(child.min_x < min_x)
			min_x = child.min_x;
		if(child.min_y < min_y)
			min_y = child.min_y;
		if(child.max_x > max_x)
			max_x = child.max_x;
		if(child.max_y > max_y)
			max_y = child.max_y;
	}
	origin.min_x = min_x;
	origin.min_y = min_y;
	origin.max_x = max_x;
	origin.max_y = max_y;
	root->NShape = origin;				//将新边界值赋予root
}

int enLargePerimeter(Node *origin, Node *curr)		//返回加入curr节点后的周长变化值
{
	Shape oS = origin->NShape;
	int min_x = oS.min_x;
	int min_y = oS.min_y;
	int max_x = oS.max_x;
	int max_y = oS.max_y;
	int oP = (max_x - min_x + max_y - min_y)*2;
	int x = curr->x;
	int y = curr->y;
	if(x < min_x)	min_x = x;
	if(y < min_y)	min_y = y;
	if(x > max_x)	max_x = x;
	if(y > max_y)	max_y = y;
	int nP = (max_x - min_x + max_y - min_y)*2;
	return nP - oP;
}

void ChoseNodeToInsert(Node *root, Node *curr)		//选择插入
{
	if(root->level == 1)				//root为第一层时
	{
		int icr = root->ChildNum;
		if(icr == NodeNum)				//当前节点已满
		{
			Node *parent = root->parent;		//获取当前节点的父节点
			Node *newNode = new_nonLeafNode();	//新建非叶节点
			Node *nowNode = root;			//获取当前节点
			SplitNode(parent, newNode, nowNode, curr);	//分裂节点
			UpdateInfomation(parent);		//更新节点信息
		}
		else
		{
			root = AddToMbr(root, curr);	//添加到R树中
			Node *father = root->parent;	//获取当前节点的父节点
			UpdateInfomation(father);	//更新插入后的信息
		}
	}
	else						//root的孩子节点为非叶节点
	{
		if(root->ChildNum == NodeNum)		//当root节点的子节点已满时
		{
			if(root->parent == NULL)	//若当前节点为根节点
			{
				//创建新节点，并将curr节点添加到这个新创建的节点中
				Node *newparent = new_nonLeafNode();
				newparent = AddToMbr(newparent, root);	//将原节点插入到newparent中
				newparent->level = root->level+1;	//层数加一
				Node *newNode = new_nonLeafNode();
				newNode->level = root->level;
				Node *nowNode = root;
				SplitNode(newparent, newNode, nowNode, curr);
				root = newparent;
				rtree = root;				//设置根节点
				ChoseNodeToInsert(root, curr);		//递归添加
				UpdateInfomation(root);			//更新节点信息
			}
			else
			{
				//向root中直接加入新节点
				Node *parent = root->parent;
				Node *newNode = new_nonLeafNode();
				newNode->level = root->level;
				newNode->parent = parent;
				SplitNode(parent, newNode, root, curr);
				UpdateInfomation(parent);
			}
		}
		else							//root的子节点未满
		{
			int childNum = root->ChildNum;
			int betterChoice;
			int nowChoice;
			if(root->level >= 3)
			{
				betterChoice = childNum -1;
			}
			else						//root在第二层
			{
				if(childNum == 1)			//root为根节点
					betterChoice = 0;
				else
				{
					int i, j, enlargeNum1, enlargeNum2, minenlarge;
					int enlarge = 10000;
					for(i = 0; i < childNum; i++)	//寻找范围
					{
						Node *node1 = root->child[i];
						enlargeNum1 = enLargePerimeter(node1, curr);						//最大周长
						for(j = i+1; j < childNum; j++)
						{
							Node *node2 = root->child[j];
							enlargeNum2 = enLargePerimeter(node2, curr);
							if(enlargeNum1 <= enlargeNum2)
							{
								nowChoice = i;
								minenlarge = enlargeNum1;
							}
							else
							{
								nowChoice = j;
								minenlarge = enlargeNum2;
							}
						}
						if(enlarge > minenlarge)
						{
							betterChoice = nowChoice;
							enlarge = minenlarge;
						}
					}
				}
			}
			root = root->child[betterChoice];	//找到较佳位置，进入
			ChoseNodeToInsert(root, curr);		//递归插入
		}
	}
}